In this description and claims, a “processor” is either a single-core processor or a core of a multiple-core processor (for example dual-core or quad-core processors), and a “multiprocessor machine” (also known as a multiple processor machine) is a single computer system having two or more “processors”.
A multiprocessor machine is fundamentally non-deterministic, in that each processor handles a sequence of instructions (also known as an instruction stream) but the order in which the instructions of one stream are executed relative to the instructions of another stream is not predictable.
There are several causes for this non-deterministic behavior, including, for example, variations in the environment (e.g. temperature), variations in the manufacturing of the individual processors and components that interface with the processors (e.g. crystals that dictate the precise clock rate of the system), variations in the configuration of the processors or systems (e.g. power management and user settings), the handling of asynchronous events in the machine, and the like.
For example, a first processor and a second processor may concurrently execute 600 instructions of their respective instruction streams, but there is no guarantee as to whether the first processor will execute its 412th instruction before or after the second processor executes its 415th instruction. This non-determinism exists regardless of whether the instructions streams are different or identical, and exists even if the two processors are identical.
Furthermore, if the same input is provided to the two processors on two different occasions, there is no guarantee that on both occasions the relative order in which the instructions are executed by the processors will be the same. On the first occasion, the first processor may execute its 412th instruction before the second processor executes its 415th instruction, and on the second occasion, the first processor may execute its 412th instruction after the second processor executes its 415th instruction.
Likewise, if the same input is provided to two identical multiprocessor machines, there is no guarantee that on both computers the relative order in which the instructions are executed by their processors will be the same. On one of the machines, the first processor may execute its 412th instruction before the second processor executes its 415th instruction, and on the other machine, the first processor may execute its 412th instruction after the second processor executes its 415th instruction.
Suppose that in the previous example the 412th instruction to be executed by the first processor is writing a new value to a particular region of the memory and the 415th instruction to be executed by the second processor is reading that particular region of the memory. If the first processor writes before the second processor reads, then the second processor will read the new value written by the first processor. However, if the first processor writes after the second processor reads, then the second processor will read an old value that was stored in the particular region. On most computers, memory accesses are serialized by bus arbitration and cache logic, hence simultaneous access to the same region in memory by more than one processor is typically not possible. Even if simultaneous access is possible, the results of such accesses is still non-deterministic. Therefore, multiple processors may compete for access to a particular region in memory. The order in which they are granted access by the hardware, namely the memory bus and cache logic, is not deterministic. In a typical multiprocessor machine, different instruction streams, each executing on a different processor, communicate with each other through memory. If the order in which the processors access the memory is not deterministic, then the communication among the processors is also not deterministic.
In computer science, replication refers to the use of redundant resources, such as software or hardware components, to improve reliability, fault-tolerance, and/or performance. A replicated service in a distributed computing environment is where several machines run the same application, so that it appears to a user of the service that there is a single machine running the application. Each machine in the group is a replica of the others. If any machine in the group fails, the failure is hidden and the service is still available to the user. If two or more identical multiprocessor machines are intended to be replicas of one another and are provided with the same input, the non-deterministic behavior of each machine may result in different decisions being made by the different machines. The different decisions may result in the machines having different states, which in turn, will lead to further differences in their behavior. The machines will no longer be replicas of one another.
Software testing and/or debugging may also be affected by non-determinism. If software is intended to be run on a multiprocessor machine, then the fundamental non-determinism of the multiprocessor machine may affect the testing and/or debugging of the software. It is difficult to test software if one cannot guarantee that operating the software in a particular manner with known inputs will result in the same outputs each time the test is performed.